package com.datastructure.algorithm.dac;

//分治算法:汉渃塔问题
public class Hanoitower {

    public static void main(String[] args) {

    }

    // 汉渃塔的移动的方法
    // 使用分治算法

    public void hanoiTower(int num, char a, char b, char c){
        // 如果只有一个盘
        if(num == 1){
            System.out.println("第1个盘从" + a + "->" + c);
        } else {
            // 如果我们有n >= 2的情况，我们可以看作是两个盘 最下面的盘 上面的所有盘
            // 1. 先把最上面的所有盘A->B,移动的过程会使用到C
            hanoiTower(num - 1, a, c, b);
            // 2. 把最下面的盘 A -> C
            System.out.println("第" + num + "个盘从" + a + "->" + c);
            // 3.把B塔的所有盘从 B -> C,移动过程使用到a塔
            hanoiTower(num-1,b,a,c);
        }
    }
}
